package a14_Sort;

/**
 * @Author quan
 * @Description 快速排序
 * @Date 2023/4/28 16:58
 */
public class Demo1_Quick_SortHeima {
    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quickSort(arr,0,9);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
    }

    /**
     *
     * @param arr 我们要排序的数组
     * @param i 要排序数组的开始索引
     * @param j 要排序数组的结束索引
     */
    private static void quickSort(int[] arr, int i, int j) {
        //记录数组的开始和结束索引
        int start = i;
        int end = j;

//        //递归的结束条件
        if(start >= end){
            return;
        }
        /**
         * 优化1：小数组直接使用插入排序
         */
//        if(end-start <= 64){
//            insetSort(arr);
//            return;
//        }
        /**
         * 优化2：每次取基准数的时候，取随机数。选取一个随机位置上的数字与start位置的数字交换
         */
//        int randomIndex = ThreadLocalRandom.current().nextInt(start,end);
//        System.out.println(randomIndex+"-----------");
//        swap(arr,randomIndex,start);
        //记录数组中的基准数：第一个元素
        int baseNumber = arr[start];

        //利用循环找到要交换的数字
        while (start < end){
            //end从后向前找，找到第一个小于基准数的数字
            while (true){
                /**
                 * if条件的end < = start 这里的条件是 或，要好好体会一下
                 */
                // 如果if语句走的是end <= start这个条件出来，说明end一直减小到=start的位置都没找到小于基准数的数字
                //此时下面的while循环因为满足end = start这个条件直接跳出，直接进入基准数回归这一步
                if(end <= start || arr[end] < baseNumber){
                    break;
                }
                end--;
            }
            //start从前向后找，找到第一个大于基准数的数字
            while (true){
                if(end <= start || arr[start] > baseNumber){
                    break;
                }
                start++;
            }
            //不断的交换start与end索引下的值
            swap(arr,start,end);
        }
        //此时start与end指向同一个值，循环结束。
        //需要将基准数归位：将start或者end所指的数字(因为两个指向的其实是同一个数)与基准数(数组的第一个值)交换
        swap(arr,start,i);

        //第一轮排序已经结束，此时将基准数的两个左右区间排序即可：递归调用
        //确定6左边的范围，重复刚才的过程
        quickSort(arr,i,start-1);
        //确定6右边的范围，重复刚才的过程
        quickSort(arr,start+1,j);
    }
    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //插入排序
    public static void insetSort(int[] arr){
        //有序区间[0,i)
        //无序区间[i,n)
        for (int i = 1; i < arr.length; i++) {
            //i当前无序区间的第一个值，j表示有序区间新增的值，然后每次新增一个值就要往前看不断调整有序区间使之有序。
            for (int j = i; j >= 1; j--) {
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }
}
